home *** CD-ROM | disk | FTP | other *** search
/ Internet Info 1994 March / Internet Info CD-ROM (Walnut Creek) (March 1994).iso / networking / ip / ka9q / osrc.arc / ALLOC.C < prev    next >
Encoding:
C/C++ Source or Header  |  1989-03-27  |  11.9 KB  |  504 lines
  1. /* memory allocation routines
  2.  *
  3.  * Adapted from alloc routine in K&R; memory statistics and interrupt
  4.  * protection added for use with net package. Must be used in place of
  5.  * standard Turbo-C library routines because the latter check for stack/heap
  6.  * collisions. This causes erroneous failures because process stacks are
  7.  * allocated off the heap.
  8.  */
  9.  
  10. #include <stdio.h>
  11. #include <dos.h>
  12. #include "global.h"
  13. #include "proc.h"
  14.  
  15. static unsigned long memfail;    /* Count of allocation failures */
  16. static unsigned long allocs;    /* Total allocations */
  17. static unsigned long frees;    /* Total frees */
  18. static unsigned long garbage;    /* Total calls to free with garbage arg */
  19.  
  20. #ifdef    LARGEDATA
  21.  
  22. /**** LARGE DATA MODEL VERSION ****/
  23.  
  24. union header {
  25.     struct {
  26.         union header huge *ptr;
  27.         unsigned long size;
  28.     } s;
  29.     long l[2];
  30. };
  31.  
  32. typedef union header HEADER;
  33. #define    NULLHDR    (HEADER huge *)NULL
  34.  
  35. #define    ABLKSIZE    (sizeof (HEADER))
  36.  
  37. HEADER huge *morecore();
  38. void *sbrk();
  39. void free();
  40. unsigned long coreleft();
  41.  
  42. static HEADER base;
  43. static HEADER huge *allocp = NULLHDR;
  44. static char huge *heapbase;
  45. static char huge *heaptop;
  46. static unsigned long heapsize;
  47.  
  48. /* Allocate block of 'nb' bytes */
  49. void *
  50. malloc(nb)
  51. unsigned nb;
  52. {
  53.     register HEADER huge *p, huge *q;
  54.     register unsigned nu;
  55.     char i_state;
  56.  
  57.     if(nb == 0)
  58.         return NULL;
  59.     i_state = dirps();
  60.     /* Round up to full block, then add one for header */
  61.     nu = ((nb + ABLKSIZE - 1) / ABLKSIZE) + 1;
  62.     if ((q = allocp) == NULLHDR){
  63.         base.s.ptr = allocp = q = &base;
  64.         base.s.size = 1;
  65.     }
  66.     for (p = q->s.ptr; ; q = p, p = p->s.ptr){
  67.         if (p->s.size >= nu){
  68.             /* This chunk is at least as large as we need */
  69.             if (p->s.size <= nu + 1){
  70.                 /* This is either a perfect fit (size == nu)
  71.                  * or the free chunk is just one unit larger.
  72.                  * In either case, alloc the whole thing,
  73.                  * because there's no point in keeping a free
  74.                  * block only large enough to hold the header.
  75.                  */
  76.                 q->s.ptr = p->s.ptr;
  77.             } else {
  78.                 /* Carve out piece from end of entry */
  79.                 p->s.size -= nu;
  80.                 p += p->s.size;
  81.                 p->s.size = nu;
  82.             }
  83.             allocp = q;
  84.             p->s.ptr = p;    /* for auditing */
  85.             restore(i_state);
  86.             allocs++;
  87.             return (void *)(p + 1);
  88.         }
  89.         /* Don't call the system for more memory if interrupts
  90.          * are off; we're probably in an interrupt handler
  91.          */
  92.         if (p == allocp && (!i_state || (p = morecore(nu)) == NULLHDR)){
  93.             memfail++;
  94.             restore(i_state);
  95.             return NULL;
  96.         }
  97.     }
  98. }
  99. /* Get more memory from the system and put it on the heap */
  100. HEADER huge *
  101. morecore(nu)
  102. unsigned nu;
  103. {
  104.     register char huge *cp;
  105.     register HEADER huge *up;
  106.  
  107.     /* Before calling main, the Turbo startup routines call malloc to
  108.      * save the environment. In turn this calls morecore, all before we
  109.      * get a chance to call grabcore. Hence the null test for heaptop.
  110.      */
  111.     if(heaptop != NULL && (char huge *)sbrk(0) >= heaptop)
  112.         return NULLHDR;    /* Don't let it overwrite stack */
  113.     if ((int)(cp = (char huge *)sbrk(nu * ABLKSIZE)) == -1)
  114.         return NULLHDR;
  115.     up = (HEADER *)cp;
  116.     up->s.size = nu;
  117.     up->s.ptr = up;    /* satisfy audit */
  118.     free((void *)(up + 1));
  119.     return allocp;
  120. }
  121. /* Grab the specified amount of memory from the system, if available,
  122.  * and place it on the heap
  123.  */
  124. unsigned long
  125. grabcore(size)
  126. unsigned long size;
  127. {
  128.     register HEADER huge *up;
  129.  
  130.     /* Find out where the break is */
  131.     heapbase = (char huge *)sbrk(0);
  132.     /* Now try to get the requested amount, or as much as possible
  133.      * below that
  134.      */
  135.     while((int)brk(heapbase+size) == -1)
  136.         size -= 256;
  137.  
  138.     heapsize = size;
  139.     heaptop = (char huge *)sbrk(0);
  140.  
  141.     /* Initialize the heap pointers */
  142.     if (allocp == NULLHDR){
  143.         base.s.ptr = allocp = &base;
  144.         base.s.size = 1;
  145.     }
  146.     up = (HEADER *)heapbase;
  147.     up->s.size = heapsize / sizeof(HEADER);
  148.     up->s.ptr = up;    /* satisfy audit */
  149.     free((void *)(up + 1));
  150.     return heapsize;
  151. }
  152.  
  153. /* Put memory block back on heap */
  154. void
  155. free(blk)
  156. void *blk;
  157. {
  158.     register HEADER huge *p, huge *q;
  159.     unsigned short huge *ptr;
  160.     char i_state;
  161.  
  162.     if(blk == NULL)
  163.         return;        /* Required by ANSI */
  164.     i_state = dirps();
  165.     p = (HEADER huge *)blk - 1;
  166.     /* Audit check */
  167.     if(p->s.ptr != p){
  168.         ptr = (unsigned short *)&blk;
  169.         printf("WARNING!! freeing garbage (0x%lx) pc = 0x%x %x proc %s\n",ptol(blk),
  170.             ptr[-1],ptr[-2],Curproc->name);
  171.         garbage++;
  172.         restore(i_state);
  173.         return;
  174.     }
  175.     /* Search the free list looking for the right place to insert */
  176.     for(q = allocp; !(p > q && p < q->s.ptr); q = q->s.ptr){
  177.         /* Highest address on circular list? */
  178.         if(q >= q->s.ptr && (p > q || p < q->s.ptr))
  179.             break;
  180.     }
  181.     if(p + p->s.size == q->s.ptr){
  182.         /* Combine with front of this entry */
  183.         p->s.size += q->s.ptr->s.size;
  184.         p->s.ptr = q->s.ptr->s.ptr;
  185.     } else {
  186.         /* Link to front of this entry */
  187.         p->s.ptr = q->s.ptr;
  188.     }
  189.     if(q + q->s.size == p){
  190.         /* Combine with end of this entry */
  191.         q->s.size += p->s.size;
  192.         q->s.ptr = p->s.ptr;
  193.     } else {
  194.         /* Link to end of this entry */
  195.         q->s.ptr = p;
  196.     }
  197.     allocp = q;
  198.     restore(i_state);
  199.     frees++;
  200. }
  201.  
  202. #ifdef    notdef    /* Not presently used */
  203. /* Move existing block to new area */
  204. void *
  205. realloc(area,size)
  206. void *area;
  207. unsigned size;
  208. {
  209.     unsigned osize;
  210.     HEADER huge *hp;
  211.     char huge *cp;
  212.     char i_state;
  213.  
  214.     hp = ((HEADER *)area) - 1;
  215.     osize = (hp->s.size -1) * ABLKSIZE;
  216.  
  217.     /* Make sure nobody else comes in and takes it */
  218.     i_state = dirps();
  219.     free(area);
  220.     if((cp = malloc(size)) != NULL && cp != area)
  221.         memcpy((char *)cp,(char *)area,size>osize? osize : size);
  222.     restore(i_state);
  223.     return cp;
  224. }
  225. #endif
  226. /* Allocate block of cleared memory */
  227. void *
  228. calloc(nelem,size)
  229. unsigned nelem;    /* Number of elements */
  230. unsigned size;    /* Size of each element */
  231. {
  232.     register unsigned i;
  233.     register char *cp;
  234.  
  235.     i = nelem * size;
  236.     if((cp = malloc(i)) != NULL)
  237.         memset(cp,0,i);
  238.     return cp;
  239. }
  240. /* Print free list map */
  241. memstat()
  242. {
  243.     HEADER huge *p;
  244.     unsigned long total = 0;
  245.     int i = 0;
  246.  
  247.     for(p = base.s.ptr;p != &base;p = p->s.ptr){
  248.         total += p->s.size * sizeof(HEADER);
  249.         printf("%5lx %6lu",ptol((void *)p),p->s.size * ABLKSIZE);
  250.         if(++i == 4){
  251.             i = 0;
  252.             putchar('\n');
  253.         } else
  254.             printf(" | ");
  255.     }
  256.     if(i != 0)
  257.         putchar('\n');
  258.     printf("heap base %lx size %lu avail %lu (%lu%%) coreleft %lu\n",
  259.      ptol((void *)heapbase),heapsize,total,100L*total/heapsize,
  260.      coreleft());
  261.     printf("allocs %lu frees %lu (diff %lu) mfails %lu garbage %lu\n",
  262.         allocs,frees,allocs-frees,memfail,garbage);
  263. }
  264. #else    /* not LARGEDATA */
  265.  
  266. /**** SMALL DATA MODEL VERSION ****/
  267.  
  268. union header {
  269.     struct {
  270.         union header *ptr;
  271.         unsigned int size;
  272.     } s;
  273.     long l;
  274. };
  275.  
  276. typedef union header HEADER;
  277. #define    NULLHDR    (HEADER *)NULL
  278.  
  279. #define    ABLKSIZE    (sizeof (HEADER))
  280.  
  281. HEADER *morecore();
  282. void *sbrk();
  283. void free();
  284. unsigned coreleft();
  285.  
  286. static HEADER base;
  287. static HEADER *allocp = NULLHDR;
  288. static char *heapbase;
  289. static char *heaptop;
  290. static unsigned long heapsize;
  291.  
  292. /* Allocate block of 'nb' bytes */
  293. void *
  294. malloc(nb)
  295. unsigned nb;
  296. {
  297.     register HEADER *p, *q;
  298.     register unsigned nu;
  299.     char i_state;
  300.  
  301.     if(nb == 0)
  302.         return NULL;
  303.     i_state = dirps();
  304.     /* Round up to full block, then add one for header */
  305.     nu = ((nb + ABLKSIZE - 1) / ABLKSIZE) + 1;
  306.     if ((q = allocp) == NULLHDR){
  307.         base.s.ptr = allocp = q = &base;
  308.         base.s.size = 1;
  309.     }
  310.     for (p = q->s.ptr; ; q = p, p = p->s.ptr){
  311.         if (p->s.size >= nu){
  312.             /* This chunk is at least as large as we need */
  313.             if (p->s.size <= nu + 1){
  314.                 /* This is either a perfect fit (size == nu)
  315.                  * or the free chunk is just one unit larger.
  316.                  * In either case, alloc the whole thing,
  317.                  * because there's no point in keeping a free
  318.                  * block only large enough to hold the header.
  319.                  */
  320.                 q->s.ptr = p->s.ptr;
  321.             } else {
  322.                 /* Carve out piece from end of entry */
  323.                 p->s.size -= nu;
  324.                 p += p->s.size;
  325.                 p->s.size = nu;
  326.             }
  327.             allocp = q;
  328.             p->s.ptr = p;    /* for auditing */
  329.             restore(i_state);
  330.             allocs++;
  331.             return (void *)(p + 1);
  332.         }
  333.         if (p == allocp && (p = morecore(nu)) == NULLHDR){
  334.             memfail++;
  335.             restore(i_state);
  336.             return NULL;
  337.         }
  338.     }
  339. }
  340. /* Get more memory from the system and put it on the heap */
  341. HEADER *
  342. morecore(nu)
  343. unsigned nu;
  344. {
  345.     register char *cp;
  346.     register HEADER *up;
  347.  
  348.     /* Before calling main, the Turbo startup routines call malloc to
  349.      * save the environment. In turn this calls morecore, all before we
  350.      * get a chance to call grabcore. Hence the null test for heaptop.
  351.      */
  352.     if(heaptop != NULL && (char *)sbrk(0) >= heaptop)
  353.         return NULLHDR;    /* Don't let it overwrite stack */
  354.     if ((int)(cp = (char *)sbrk(nu * ABLKSIZE)) == -1)
  355.         return NULLHDR;
  356.     up = (HEADER *)cp;
  357.     up->s.size = nu;
  358.     up->s.ptr = up;    /* satisfy audit */
  359.     free((void *)(up + 1));
  360.     return allocp;
  361. }
  362. /* Grab the specified amount of memory from the system, if available,
  363.  * and place it on the heap
  364.  */
  365. unsigned long
  366. grabcore(size)
  367. unsigned long size;
  368. {
  369.     register HEADER *up;
  370.  
  371.     /* Find out where the break is */
  372.     heapbase = (char *)sbrk(0);
  373.  
  374.     /* Now try to push it as high as possible */
  375.     while(brk(heapbase+size) == -1)
  376.         size -= 16;
  377.  
  378.     heapsize = size;
  379.     heaptop = (char *)sbrk(0);
  380.  
  381.     /* Initialize the heap pointers */
  382.     if (allocp == NULLHDR){
  383.         base.s.ptr = allocp = &base;
  384.         base.s.size = 1;
  385.     }
  386.     up = (HEADER *)heapbase;
  387.     up->s.size = heapsize / sizeof(HEADER);
  388.     up->s.ptr = up;    /* satisfy audit */
  389.     free((void *)(up + 1));
  390.     return heapsize;
  391. }
  392.  
  393. /* Put memory block back on heap */
  394. void
  395. free(blk)
  396. void *blk;
  397. {
  398.     register HEADER *p,*q;
  399.     unsigned short *ptr;
  400.     char i_state;
  401.  
  402.     if(blk == NULL)
  403.         return;        /* Required by ANSI */
  404.     i_state = dirps();
  405.     p = (HEADER *)blk - 1;
  406.     /* Audit check */
  407.     if(p->s.ptr != p){
  408.         ptr = (unsigned short *)&blk;
  409.         printf("WARNING!! freeing garbage (0x%lx) pc = 0x%x %x proc %s\n",ptol(blk),
  410.             ptr[-1],ptr[-2],Curproc->name);
  411.         garbage++;
  412.         restore(i_state);
  413.         return;
  414.     }
  415.     /* Search the free list looking for the right place to insert */
  416.     for(q = allocp; !(p > q && p < q->s.ptr); q = q->s.ptr){
  417.         /* Highest address on circular list? */
  418.         if(q >= q->s.ptr && (p > q || p < q->s.ptr))
  419.             break;
  420.     }
  421.     if(p + p->s.size == q->s.ptr){
  422.         /* Combine with front of this entry */
  423.         p->s.size += q->s.ptr->s.size;
  424.         p->s.ptr = q->s.ptr->s.ptr;
  425.     } else {
  426.         /* Link to front of this entry */
  427.         p->s.ptr = q->s.ptr;
  428.     }
  429.     if(q + q->s.size == p){
  430.         /* Combine with end of this entry */
  431.         q->s.size += p->s.size;
  432.         q->s.ptr = p->s.ptr;
  433.     } else {
  434.         /* Link to end of this entry */
  435.         q->s.ptr = p;
  436.     }
  437.     allocp = q;
  438.     restore(i_state);
  439.     frees++;
  440. }
  441.  
  442. #ifdef    notdef    /* Not presently used */
  443. /* Move existing block to new area */
  444. void *
  445. realloc(area,size)
  446. void *area;
  447. unsigned size;
  448. {
  449.     unsigned osize;
  450.     HEADER *hp;
  451.     char *cp;
  452.     char i_state;
  453.  
  454.     hp = ((HEADER *)area) - 1;
  455.     osize = (hp->s.size -1) * ABLKSIZE;
  456.  
  457.     /* Make sure nobody else comes in and takes it */
  458.     i_state = dirps();
  459.     free(area);
  460.     if((cp = malloc(size)) != NULL && cp != area)
  461.         memcpy((char *)cp,(char *)area,size>osize? osize : size);
  462.     restore(i_state);
  463.     return cp;
  464. }
  465. #endif
  466. /* Allocate block of cleared memory */
  467. void *
  468. calloc(nelem,size)
  469. unsigned nelem;    /* Number of elements */
  470. unsigned size;    /* Size of each element */
  471. {
  472.     register unsigned i;
  473.     register char *cp;
  474.  
  475.     i = nelem * size;
  476.     if((cp = malloc(i)) != NULL)
  477.         memset(cp,0,i);
  478.     return cp;
  479. }
  480. /* Print free list map */
  481. memstat()
  482. {
  483.     HEADER *p;
  484.     unsigned long total = 0;
  485.     int i = 0;
  486.  
  487.     for(p = base.s.ptr;p != &base;p = p->s.ptr){
  488.         total += p->s.size * sizeof(HEADER);
  489.         printf("%5lx %6lu",ptol(p),(long)p->s.size * ABLKSIZE);
  490.         if(++i == 4)
  491.             putchar('\n');
  492.         else
  493.             printf(" | ");
  494.     }
  495.     if(i != 0)
  496.         putchar('\n');
  497.     printf("heap base %lx size %lu avail %lu (%lu%%) coreleft %u\n",
  498.      ptol((void *)heapbase),heapsize,total,100L*total/heapsize,coreleft());
  499.     printf("allocs %lu frees %lu (diff %lu) mfails %lu garbage %lu\n",
  500.         allocs,frees,allocs-frees,memfail,garbage);
  501. }
  502. #endif
  503.  
  504.